/*
 * shortestpath.c
 *
 *  Created on: Apr 7, 2011
 *      Author: Marco Luisi
 */

#define INF -1.0

#include <float.h>
#include <errno.h>
#include <string.h>
#include <stdlib.h>
#include "dgraph.h"
#include "shortestpath.h"
#include "error_checks.h"

void relax(unsigned int, graph_t *, unsigned int *, double *);
unsigned int extract_min_array(double *, unsigned int);

//da spostare se si tiene

typedef struct {
	unsigned int bit : 1;
} bit_s;

//typedef struct{
//	bit_s bits[128]; //cambiare la dim
//};

/** implementa l'algoritmo di Dijkstra per la ricerca di tutti i cammini minimi a patire
    da un nodo sorgente
    \param g grafo pesato, con parametri non negativi
    \param source nodo da cui calcolare i cammini minimi
    \param pprec puntatore di puntatore: (1)
           se pprec != da NULL viene assegnato a *pprec
           il vettore dei predecessori definito come segue:
	   per ogni nodo n1
	               *pprec[n1] = n2
	   se n2 e' il nodo che precede n1 nel cammino minimo da source a n1
	   (2) se pprec == NULL il vettore non viene assegnato (non e' un errore)


    \retval dist puntatore al vettore delle distanze minime calcolate (se tutto e' andato bene )
    \retval NULL se si \'e verificato un errore, setta errno
*/
double* dijkstra (graph_t* g, unsigned int source, unsigned int** pprec){

	double *dst_vect = NULL;
	double distance;
	bool_t *in_queue;
	bool_t go;

	edge_t *e;

	unsigned int i = 0;
	unsigned int q;
	unsigned int node;
	unsigned int nodes;
	unsigned int *pred = NULL;
	unsigned int queue_size;

	double min;

	if(g == NULL){
		errno = EINVAL;
		return NULL;
	}

	in_queue = malloc(g->size * sizeof(bool_t));//EC
	for(i = 0; i < g->size; i++){
		in_queue[i] = TRUE;
	}


	/*Inizializzazione vettore dei predecessori*/
	pred = malloc(g->size * sizeof(unsigned int));
	if (pred == NULL){
		errno = ENOMEM;
		return NULL;
	}

	for (i = 0; i< g->size; i++){
		pred[i] = UNDEF;
	}

	/*Inizializzazione vettore delle distanze*/
	dst_vect = malloc(g->size * sizeof(double));
	if (dst_vect == NULL){
		errno = ENOMEM;
		return NULL;
	}
	for (i = 0; i< g->size; i++){
		dst_vect[i] = DBL_MAX;
	}


	/*Inizializzazione nodo radice*/
	dst_vect[source] = 0;
	q = g->size;
	//BITMAAAP!!

	//ciclo su Q se tutti in visited sono true esce
	nodes = g->size;
	/*Estrazione nodo con distanza minore dalla radice */
	go = TRUE;
	//printf("DIJK radice %d\n",source);
	queue_size = g->size;
	while(queue_size  > 0){//cambiare guardia?
		node = nodes +1;// togliere?
		min = DBL_MAX;
		/*Estrazione del nodo in coda con la distanza minore*/
		for( i = 0; i < nodes; i++){
			if(in_queue[i] == TRUE){
				//printf("inqueue TRUE dst = %f\n",dst_vect[i]);
				//printf("dst != INFINITY\n");
					if(dst_vect[i] < min){
						min = dst_vect[i];
						node = i;
						//printf("aggiornato min\n");
					}
			}
		} /*Fine scansione coda*/

		//printf("min è %f del nodo %d\n", min, node);

		if (min == DBL_MAX ){//basta quello sotto?
			//go = FALSE;
			break; //basta?
		}

		/*Estrazione nodo dalla coda*/
		in_queue[node] = FALSE; //prima era i
		queue_size -- ;
		e = g->node[node].adj;
		while(e != NULL){
			if (in_queue[e->label] == TRUE){//vicini presenti nella coda
				distance = dst_vect[node] + e->km;
				if (distance < dst_vect[e->label]){ /*Si aggiorna predecessore e valore distanza*/
					dst_vect[e->label] = distance;
					pred[e->label] = node;
				}
			}
			e = e->next;

		} //fine ciclo sull'adiacenza

	}//fine while PRINCIPALE


	//controlo su prec!!!!!!

	if(pprec == NULL){
		//FARE free?
		free(pred);
	}
	else {

		*pprec = pred;
	}

	//POI TOGLIERE
	for(i = 0; i < g->size; i++){
		if(dst_vect[i] == DBL_MAX)
			dst_vect[i] = INFINITY;
	}

	free(in_queue);
	return dst_vect;
}



unsigned int extract_min_array(double *vect, unsigned int sz){


}

void relax (unsigned int idx, graph_t *g, unsigned int * queue, double *dst_vect){

	node_t *node;
	edge_t *adj;
	double len;

	node = &(g->node[idx]);
	adj = node->adj;

	while(adj != NULL){

		if(queue[adj->label] == 0){  //si controlla che sia SEMPRE nella coda
			len =  dst_vect[idx] + adj->km; //
			if(dst_vect[adj->label] == INF || dst_vect[adj->label] > len){
				dst_vect[adj->label] = len;
			}


		}

		adj = adj->next;
	}



	return;
}



/** crea la stringa della rotta da n1 a n2 usando l'array delle precedenze calcolato da dijkstra
    \param g
    \param n1
    \param n2
    \param prec

    \retval rotta puntatore alla stringa che descrive la rotta se tutto e' andato bene
    rotta contiene tutte le citta attraversate separate da '$' n1$citta1$....$cittaN$n2
    ad esempio rotta da PISA ad AREZZO PISA$LUCCA$PRATO$FIRENZE$AREZZO
    \retval NULL se la rotta da n1 a n2 non esiste (errno == 0) e
    se si e' verificato un errore (errno != 0)
 */
char * shpath_to_string(graph_t * g, unsigned int n1, unsigned int n2,  unsigned int * prec){

	char **labels = NULL;
	char *path = NULL;
	bool_t found = FALSE;
	int lenght;
	unsigned int tmp;
	unsigned int dim;
	unsigned int index;
	unsigned int i;
	unsigned int j;

	/*Controllo dei parametri*/
	if( g == NULL){
		errno = EINVAL;
		return NULL;
	}
	if( prec == NULL){
		errno = EINVAL;
		return NULL;
	}
	if( n1 > g->size){
		errno = EINVAL;
		return NULL;
	}
	if( n2 > g->size){
		errno = EINVAL;
		return NULL;
	}
	//printf("path to str da %d a %d\n",n1,n2);
	/*Si inserisce il nodo destinazione*/
	MALLOC(labels,g->size,sizeof(char*));//size esaagerato?!?!
	dim = 1;
	labels[0] = g->node[n2].label;
	lenght = strlen(labels[0]);
	index = prec[n2];

	//printf("prima label !%s! primo index %d\n",labels[0], index);
	/*Ciclo di ricerca a ritroso del cammino*/
	for(i = 1; i < g->size; i++){
		/*Percorso inesistente*/
		if (index == -1){
			errno = 0;
			free(path);//messo dopo
			path = NULL;
			free(labels);
			return NULL;
		}

		labels[i] = g->node[index].label;
		//printf("label %d !%s!\n",i, labels[i]);
		lenght += strlen(labels[i]);

		if(index == n1){//trovato
			found = TRUE;
			break;
		}
		/*Nodo non trovato si prosegue*/
		index = prec[index];
    } // fine for

	/*Stampa del percorso*/
	lenght = lenght + i +1;

	if(path != NULL){
		printf("path NON NULL !%s!strlen %d\n",path,strlen(path));
	}

	//MALLOC(path,lenght,char);
	//path = malloc(lenght * sizeof(char));
	path = calloc(lenght,sizeof(char));
	//printf("path prima delle junte !%s! lungo %d\n",path,strlen(path));
	for(j = i; j > 0; j--){
		//printf("aggiunta di !%s!\n",labels[j]);
		strcat(path,labels[j]);
		strcat(path,"$");
		}
		strcat(path,labels[0]);

	free(labels);
	//printf("path restituito !%s!\n",path);
	return path;
}

